COMPUTER VISION
    				  
		 Thomas O. Binford, Stanford University 
				and
		Jay M. Tenenbaum, Stanford Research Institute


			Introduction

"Intelligent" computers require knowledge of their  environment,  and
the  most  effective  means of acquiring such knowledge is by seeing.
Vision opens a new realm of computer applications.  Weather  analysis
from  cloud  maps  and  medical  diagnosis from x-rays and blood cell
counts are two of many high volume data processing tasks that require
pictorial  input.  Man-machine communication will be facilitated if a
person can directly show the computer  a  real  object,  rather  than
describe  it symbolically.  Designers, for example, could then easily
obtain a computerized structural analysis of scale models.

A particularly exciting area of application is industrial automation.
Today  in  industry  there are hundreds of machines called industrial
robots.   These programmable manipulators can repetitively execute  a
precise  sequence of motions, but have no sensors and are thus unable
to react dynamically  to  contingencies.      Simple  sensors  and  a
minicomputer   could,   at   slight   additional   cost,  turn  these
manipulators into true robots. With primitive visual  skills,machines
could align mating parts in assembly operations, increase reliability
by self-calibration, detect flaws, and avoid disasters.   Vision will
also  minimize  the  present need for precise positioning of parts at
each work station; parts could instead be transported in  a  bin  and
picked out as needed.

The  study  of  perception also provides valuable insights into human
and machine information processing. Many of the problems  encountered
are   fundamental  to  intelligent  activity.  For  example,  how  is
knowledge represented?     How does  knowledge  provide  guidance  in
drawing  conclusions  from  perceptual  data?     How  does  existing
knowledge interact with conclusions drawn from an  image  to  acheive
learning?   Questions  that  arise  in  the  implementation of vision
systems have broad relevance to  computer  science:    How  shoulc  a
complex  task  be  partitioned  into modules?  How should the modules
communicate to share their knowledge and special capabilities?    How
should  systems  with  highly interdependent modules be structured to
facilitate modification?

Techniques developed for machine perception cannot be taken literally
as  models  for biological systems because of differences in hardware
and gaps in our knowledge.    However,  fundamental  limitations  are
shared, suggesting that some of the principles might also be found in
nature.   Computer vision research may, in turn, occasionally  borrow
from biology, but we cannot copy nature, since again, the details are
not yet known and the hardware is different.


Historically,   computer   vision  emerged  from  the  study  of  two
dimensional pattern recognition.  However, it is seldom  possible  to
apply the mathematical formalisms developed for classification to the
analysis of real scenes.   Consider the visual  requirements  for  an
organism  such  as  a robot. It must manipulate or avoid objects, not
just classify them.         Manipulation  requires  three-dimensional
interpretations  and  spatial relations of objects.  In problems such
as character recognition, it was attractive to simply save images  or
feature vectors, and then match against an image or part of an image.
But in real scenes, objects occlude one another, they have parts with
joints that move separately, there are many viewpoints, many possible
objects, and many combinations of objects. Object classes,  moreover,
are  often  defined by function, not shape (e.g., the class of coffee
cups).     Direct template matching techniques  are  impractical  for
these requirements, except in very carefully controlled applications.
Perception involves complex deductions  in  order  to  understand  an
image in terms of a priori knowledge of the world.
		ELEMENTS OF A VISUAL SYSTEM

The computer eye is usually some form of TV camera with color filters
and  a  turret  or  zoom  lens  for  closeup views.      The computer
controls filters, lens and other parameters to optimize the image for
each  task [1].   A recent study has suggested alternative sensors to
overcome the inadequate dynamic  range  of  television  systems  [2].
Range  information  greatly  simplifies the interpretation of scenes.
Humans use depth information obtained from stereo and  a  variety  of
inferred  cues such as motion parallax and the size of known objects.
Since these techniques require subtantial processing,  it  is  easier
for  machines  to obtain depth by direct measurement.   Several depth
sensors based on triangulation have been built [3, 4].

A TV image is read into memory  as  an  array  of  brightness  values
(typically  300x300) with 4 to 8 bits for each sample for each color.
Computer vision can be thought of as the process of transforming this
mass  of numbers into a symbolic description. The translation process
can   be   subdivided   into   segmentation,   representation,    and
interpretation.

The  process  of  segmentation  partitions  a  scene  into meaningful
entities that may be  recognizable.       Segmentation  in  character
recognition   is  simple,  since  printed  characters  are  spatially
separated and have high contrast with white paper. It  is  harder  to
segment  objects  in  a real scene (even simple scenes) since objects
may overlap  and  will  not  usually  be  separable  from  the  local
background by a single attribute like brightness contrast.   Instead,
segmentation must proceed by seeking regions of  uniform  brightness,
color,  or  texture  (itself  a  complex descriptor), or regions with
regular boundaries.   Segmentation may also depend on inferred  depth
cues (e.g., texture gradients or suspected occlusion).

In what form can we represent objects internally in the computer? The
simplest form is a pictorial template, an array of brightness  values
to  be  matched  directly against fragments of scenes by correlation.
Given the inadequacies  of  this  representation,  we  must  describe
partitioned  regions symbolically in terms of extracted features such
as color, size,  texture,  and  shape.    These  properties  must  be
inferred from the image by complex processes.  Simple descriptors for
shape or texture may be used in simple  tasks  and  limited  context.
Shape might be described by the ratio of the squared perimeter to the
area of a region.  More sophisticated shape  representations,  needed
for a wider range of tasks, are described later.

Interpretation  is  often  expressed  as computing a distance measure
between an object and a stored model.  For simple cases that approach
can be useful.     When objects are occluded, there must be a partial
match. When objects are not identical, judgments of similarity depend
on  representation  of shape and representation of the task, in order
to define important differences.   The most  useful  approach  is  to
build  up  symbolic  descriptions  and  make symbolic descriptions of
differences.     Sometimes there are  sufficiently  few  models  that
matching  with  each  model is possible. More generally, the observed
features must first be used to retrieve likely models  from  a  large
visual memory.

The integration of segmentation, representation and interpretation to
achieve perception is illustrated by a system built at the University
of  Edinburgh  [5] that can recognize a small set of ordinary objects
such as pencils, eyeglasses  and  teacups.    Objects  are  presented
against  a  contrasting  background.    Segmentation  is  achieved by
partitioning the scene into regions of  uniform  brightness.  Objects
are  represented  by  relational  graphs  detailing  gross attributes
(e.g., size and  shape)  of  their  principal  regions  and  pairwise
constraints   between  these  regions  (e.g.,  above,  larger  than).
Interpretation  is  accomplished  by  mapping  the  relational  graph
descriptions  of  known  objects  onto the segmented regions obtained
from the scene, and seeking the best match.

Experience with early bottom-up systems  of  this  type  led  to  the
realization  that  the  three  basic processes of a perceptual system
were highly interdependent; one cannot proceed  sequentially  through
segmentation, representation, and interpretation and expect to obtain
a globally consistent interpretation for all objects in a scene.  One
problem  is  that  no  reliable  basis  exists for judging the global
significance  of  segmentation  boundaries  using  local   similarity
criteria.   Segmentation  must  be guided by interpretation to choose
among many alternative partitionings, the alternative that leads to a
globally  consistent and reasonable description of the scene.  A nice
exposition of these ideas is given by Minsky [6].

			BLOCKS WORLD

To avoid some of these difficulties, research concentrated  initially
on  scenes  of  toy  blocks.   Roberts' [7] important work opened the
field.   Objects were represented as  built  up  of  three  primitive
parts,  a  block, a wedge, and a hexagonal prism. The program assumed
that it would first obtain  perfect  line  drawings.   Interpretation
meant   choosing   a  stored  three-dimensional  model  which,  after
translation, rotation, and scaling, could be projected to match  part
of  the  image.   The  recognized  piece  was  then  cut away and the
remainder considered.  Primitives were represented by their  vertices
in  three  dimensions. To decide on likely image points that belonged
to a single  body,  the  program  attempted  to  identify  unobscured
polygons,  and  then  match sets of vertices to topologically similar
model vertices.  Line drawings were formed by  a  sequence  of  local
operations.   Candidate  edge  points were considered by thresholding
the gradient of intensity.   Isolated  edge  points  were  discarded.
Connected  line  fragments  were  concatenated  into  lines that were
segmented at corners by a sequential least squares line fit.  Merging
of collinear lines bridged some gaps.

That  system  organization has proven inadequate. It is not enough to
use models and template matching. Producing perfect line drawings  is
not  practical.     Some  lines  are missed; shadows, reflections and
surface markings cause extra lines; errors  made  at  one  stage  are
compounded  by later stages.  These deficiencies motivated subsequent
research.

Guzman [8] found it possible to segment complex scenes  into  objects
without template matching, by observing that some vertices give local
evidence that adjacent regions belong to the same body. In Figure  1,
vertices A,B,C,E,G,H and I give evidence that adjacent regions belong
to the same body, while vertex F does not.  Vertex D, which resembles
G,  gives  misleading  evidence.     To  avoid such coincidences, the
program required confirmation.      Regions linked twice were  joined
into  clusters;  regions  linked twice to a cluster were also joined.
Regions linked only to a single cluster  were  also  joined  to  that
cluster.   Eventually  the  program  evolved  to  include inhibitions
against certain links by requiring similar conditions at both ends of
a line.  Other links were introduced without much motivation.

This  program  was an important advance.    Bodies could be segmented
without recognition and without explicit models.    The  program  did
surprisingly   well,   but   had   problems   with  holes  and  other
non-convexities, and with accidental  alignment.     being  told  the
background.     Guzman  also  could not cope well with imperfect line
drawings. For example, in the case of Figure 2 his program would fail
because  a  missing line makes region R3 common to both the block and
wedge.  Falk [9] was able to avoid some of the errors associated with
missing  boundaries  by using an approach resembling Guzman's to link
line segments likely to belong to the same object instead of regions.

The limited generality of both these programs was  due  to  the  fact
that  they  were implemented as a collection of ad hoc heuristics for
segmentation with no explicit understanding of line drawings.   Thus,
while  Falk himself realized that regions like R3 were non-planer and
could not arise in a scene  containing  only  trihedral  solids,  his
program  could not reason at this level. Huffman [10] and Clowes [11]
made theoretical analyses of objects  with  only  trihedral  vertices
(three  planes at each vertex).  Using these analyses, edges could be
classified at each vertex as  convex,  concave  and  obscuring.  Some
drawings could then be rejected as impossible if a given line was not
consistently labeled at each end. Waltz [12] expanded  that  labeling
of lines to include cracks and whether adjacent regions were shadowed
or illuminated. Since each vertex could have many interpretations. it
would   seem   that  a  search  for  consistent  labelings  would  be
unmanageable.      Instead, the increased precision  of  descriptions
allows  rapid  discarding of wrong interpretations.      Not only are
solutions possible, they are quickly obtained. Instead of a  complete
tree  search,  it  was  adequate  to  consider  vertices in sequence,
eliminating inconsistent  interpretations  as  each  new  vertex  was
added.     This  produced  all  possible  interpretations of a scene.
However,  other  criteria  can  then  be  used  to  choose  the  most
reasonable  interpretation.     A detailed survey of the work through
Huffman appears in a recent text by Duda and Hart [13].





The best performance in  extracting  line  drawings  from  television
images  of polyhedra is given by the Shirai [14] and the Binford-Horn
[15] line finders.   Shirai's system performs  better,  but  requires
large contrast between objects and background (e.g., white on black),
and finds only features and objects for which cues are available from
context.      The Binford-Horn system is able to find most lines in a
scene of white blocks on a white background in arbitrary lighting. It
misses  a  few  lines,  which can usually be inferred from those that
were  found,  and  garbles  some  vertices.   The  two  systems   are
complementary and should be combined.

The two programs are based on different principles.  Shirai's program
first found the outer boundaries of an object or cluster of  objects.
It   then  tried  to  guess  additional  lines  that  were  parallel,
perpendicular, or extensions to lines already  found.     Search  for
missing lines concentrated around vertices in the preliminary drawing
where they would be most likely found. The use  of  context  involved
not  changing  thresholds, but using special-purpose operators--e.g.,
verify a line at known position and angle;  find  a  line  through  a
vertex.   Figure  3  illustrates  the complexity of scenes handled by
Shirai's program. The Binford-Horn system was intended to provide the
base  for  a  system  such  as  Shirai's  by providing a partial line
drawing without special assumptions about the scene.  It used a local
directional  edge operator and an optimal sequential decision process
to group the edge points into continuous curves.

It is interesting to compare these systems with biological ones.  The
directional  edge  operators  [16], which are scanned over the image,
are analogous to the edge-detector cells  discovered  by  Heubel  and
Wiesel[17]  in  higher  animals.       In  practice, large brightness
gradients at reflections and  on  curved  surfaces  cause  masses  of
spurious  edge  fragments.       Smooth  gradients  are eliminated by
subtracting the local average at each point,  a  process  similar  to
lateral inhibition in the retina of animals.



			REAL-WORLD VISION



The   blocks   world   illustrates  many  basic  aspects  of  machine
perception.   However, since many critical  problems  encountered  in
perceiving real-world scenes do not arise in the blocks world, few of
the techniques  developed  extend  to  the  real-world  domain.   For
example:

(1)  The  region-growing  and  edge-finding  techniques developed for
uniformly painted blocks cannot cope with the textures and variations
of brightness that predominate in the real world.

(2)  The  precise  topological descriptions that characterized simple
polyhedra are inappropriate or unobtainable for  complex  real  world
objects such as trees.

(3)  Interpretation  by  exhaustively  matching  all known prototypes
against each segmented body is not feasible  with  large  numbers  of
objects and cluttered scenes.

Description  of  simple  polyhedral scenes was difficult enough; with
these added obstacles, is there hope for success  in  perceiving  the
real  world?      Perception  in  the  blocks world sought a complete
description of everything present. It may not be  possible  (or  even
meaningful)   to  obtain  exhaustive  descriptions  of  real  scenes.
However,  complete  descriptions  are  seldom  needed;  a  system  is
typically  concerned  with  only a few objects required to complete a
specific task.

For blocks, we restricted our programs to black and white images  and
distinguished structures of blocks solely on the basis of shape.   In
the real world, there is a tremendous redundancy of visual cues.   We
can use color, texture, depth, size, and surface orientation, as well
as  shape,  whichever  distinguishes   a   particular   object   most
effectively.

Real-world  objects are usually found in well defined contexts--e.g.,
telephones  are  expected  on  tables  but  not  in  waste   baskets.
Recognition  of  a  few  prominent  landmarks, combined with a priori
knowledge of the environment can thus severely restrict what  objects
may  be present in each part of the scene. While these objects may be
difficult  to  describe,  there  will  usually  be  sufficient   cues
available  to  discriminate  easily among the alternatives.    Often,
very gross descriptions of complex  attributes  such  as  shape  will
suffice  to  discriminate among a limited number of grossly different
alternatives (e.g., a person can be distinguished from a  dog  simply
by the predominantly vertical orientation of a human body).

Real-world  vision can be viewed as a strategy problem: Given a task,
first decide where to look for objects of interest  and  then  decide
how  to  distinguish  them  from  other  objects  that  might also be
present.   The system must limit interpretations to a small subset of
possible  objects, selected on the basis of a priori expectations and
crude descriptions of the scene.     Segmentation  can  be  based  on
attributes  that  are known to be uniform over these objects. The key
problems of information overload are overcome by tightly coordinating
segmentation  and interpretation with world knowledge and task goals.
The overload problem cannot  be  solved  by  merely  building  faster
computers   and  bigger  memories;  hardware  improvements  will  aid
adequate techniques but do little for exhaustive techniques.

The principal work to date on real world vision has  concentrated  on
segmentation and representation.  Segmentation of textured scenes has
been studies as a two-dimensional problem for agricultural and  earth
resource  survey  applications.    Bajcsy  [18]  has analyzed outdoor
scenes with perspective, where three-dimensional texture descriptions
are  important.       Textures were described hierarchically in terms
of  simpler  texture  elements  and  their   spatial   relationships.
Descriptors  for  texture  elements  and  relations were derived from
Fourier analysis.   Typical attributes were directionality (if  any),
size,  contrast,  and  spacing  of texture elements.      The Fourier
transform was found troublesome,however, and color  descriptors  were
added to improve performance.  Some depth relations could be observed
from texture gradient.     An attempt was made to  obtain  consistent
interpretations  by first confirming region boundaries by independent
properties, making three-dimensional  interpretations,  and  matching
region  descriptors with those of sky, trees, grass, etc.  in a world
model.

The  quality  of  interpretation  was  limited  by  unreliability  of
region-growing  processes. Further work in outdoor scenes attempts to
incorporate the  world  model  and  interpretation  into  the  region
growing process. Regions are merged not only because of similarity of
properties, but because the consistency of semantic interpretation is
improved.


Typical  robot  tasks  such  as  manipulation,  collision  avoidance,
display,  and  recognition  were  analyzed to determine computational
primitives required for descriptions of shape.  Although  some  would
disagree, our criteria for shape representation are [19]:

(1)  Representations  should  be symbolic at a high level in order to
interface with knowledge of the problem domain.

(2) Representations should depend on segmentation into  parts,  which
may have sub-parts.

(3)  Primitives  should  be  three-dimensional  volume  descriptions,
rather than surface descriptions, to allow a natural choice of parts.

(4) Descriptions should be generative.      A  modest  collection  of
primitives should allow description of a vast set of objects.

We  will outline one representation that fulfils these desiderata for
a large class of curved objects. Objects are described  in  terms  of
components  that  are  simple  to  describe, and the relationships of
these parts.  A useful shape primitive for many curved objects is  an
arbitrary  space  curve,  and  normal  cross-sections along this axis
(Figure 4).      Snake-like objects, helices,  toroids,  and  locally
helical  and  toroidal shapes are naturally described [19]. Our basic
definition of a simple piece is that the direction  of  its  axis  be
continuous  and  that  the  cross-section function along that axis be
continuous.    We look for large changes in  the  cross-section,  and
consider  them  as  likely  places for segmenting the object.     The
segmentation  process  must  be  flexible  and   able   to   generate
alternative  propositions.     A higher-level routine will ultimately
select from the alternatives.     Figure 5  shows  an  experimentally
obtained computer description of a doll [3].

			INDUSTRIAL APPLICATIONS

Recently,  several  laboratories  have begun to apply techniques from
perception research to  practical  industrial  tasks.        Stanford
University  has  demonstrated simple assembly operations using vision
and touch. General Motors laboratories has succeeded  in  mounting  a
wheel  on  an axle. Stanford Research Institute and Hitachi Ltd. have
each demonstrated systems that can distinguish sheet metal parts on a
moving  conveyor  belt  and  determine  their  orientation  to enable
manipulation.     Template-matching  techniques  were  used  to  take
advantage of the two-dimensional nature of these tasks. Moreover, the
conveyor demonstrations relied on the contrast between shiny metallic
parts  and  the  black belt to simplify segmentation. Many industrial
processes share similar constraints or can be readily  redesigned  to
do  so.  We thus expect a proliferation of industrial applications of
computer perception in the near future.